1. Field of the Invention
This invention relates to a main memory data control or management system in a computer and, more particularly, to such a system for efficiently realizing virtualization of list structure data which are basic and indispensable in the field of symbol manipulation, such as artificial intelligence, formula manipulation or natural language manipulation.
2. Description of the Related Art
In general, in the field of symbol manipulation, such as artificial intelligence, formula processing or natural language processing, the desired symbolic manipulation is performed under control or management of data items of the list structure in a memory.
Up to now, the organization of the data of the list structure has been by means of so-called pointer-linked data in which nodes are linked together by pointers. With such pointer-linked data, a so-called binary tree structure is most popular, in which each pointer usually acts only in one direction and each node has its own data and pointers, usually two pointers, for referencing other nodes.
For example, in a LISP language, known as a representative language handling data items of the list structure, an example, of data of the list structure is shown in FIG. 1, in which each of intermediate nodes N.sub.10, N.sub.12, N.sub.14, N.sub.15, N.sub.17, N.sub.20, N.sub.22, N.sub.24 and N.sub.26 has two pointers, while concrete data all carried by terminal nodes N.sub.11, N.sub.13, N.sub.16, N.sub.18, N.sub.19, N.sub.21, N.sub.23, N.sub.25, N.sub.27 and N.sub.28, with the information being carried by the state of construction of the terminal nodes.
For handling the data of the list structure in a memory, the nodes N.sub.10, N.sub.11, N.sub.12, N.sub.13, . . . are represented in a memory space M provided with addresses, and the pointers are indicated by the addresses in the memory space M, as shown for example in FIG. 2, for computerized control of the above data.
Meanwhile, the data of the list structure handled in the field of symbol manipulation may be joined together, disconnected, expanded or contracted and thus present a dynamic structure and a trial-and-error type behavior in which the information given as the data structure is changed multifariously.
Also, when such data of the list structure is controlled in the memory by a computer, the data structure becomes scattered in the memory and new nodes in the memory may be lost or used-up so that unnecessary data may be produced. These unnecessary nodes are recovered and re-used as new nodes by way of a garbage collection.
In case of a shortage of the real memory space despite such garbage collection, the memory space M may be expanded by using a virtual memory technique, that is by virtualization. For example, as shown in FIGS. 3 and 4, the memory space is controlled or managed on a page-by-page basis, and thus a page-by-page data swapping is performed between the real memory space RM and the virtual memory space IM.
It will be noted that the current computer architecture is designed to process local data having a static structure and is not suited to manipulation of the data of the list structure used in the field of symbol manipulation. Thus an extremely long time interval is necessitated in executing the garbage collection in which the object of manipulation is scattered dynamically. On the other hand, for virtualizing the memory space, it has been customary to control the memory space on a page-by-page basis on the premise that the related data are at near-by locations. While the page represents a fixed area in the memory space, since the data of the list structure are changed dynamically, the structure is caused to lie across a plurality of pages in an intricate manner, thus resulting in frequent occurrences of page faults and a lowered efficiency. Above all, when garbage collection is performed with respect to the virtualized memory space, since the page-by-page data swapping is executed between the real memory space and the virtual memory space, the operational efficiency is lowered significantly.
In view of the above described status of the art, it is an object of the present invention to provide for efficient virtual storage of data of the list structure which are fundamental and indispensable in the field of symbol manipulation such as artificial intelligence, formula manipulation or natural language manipulation.